package com.zlk.algorithm.algorithm.sort.heap;

import com.zlk.algorithm.algorithm.sort.SortUtils;

/**
 * @program: algorithm
 * @ClassName Code02_HeapSort
 * @description:
 * @author: slfang
 * @create: 2024-12-16 15:56
 * @Version 1.0
 * // 堆结构和堆排序，填函数练习风格
 * // 测试链接 : https://leetcode.cn/problems/sort-an-array/
 **/
public class Code02_HeapSort {

    public int[] sortArray(int[] nums) {
        if(nums.length<2||nums==null){
            return nums;
        }
        for (int i = 0; i < nums.length; i++) {
            heapInsert(nums,i);
        }
        int size = nums.length;
        swap(nums,0,--size);

        while (size>0){
            heapFiy(nums,0,size);
            swap(nums,0,--size);
        }
        return nums;
    }


    //下沉
    private void heapFiy(int[] nums,int index,int size) {
        int l = (index/2)+1;
        int r = l+1;
        while (l<size){
            int maxIndex = l;
            if(r<size){
                maxIndex=nums[l]>nums[r]?l:r;
            }
            maxIndex = nums[index]>nums[maxIndex]?index:maxIndex;
            if(maxIndex==index){
                return ;
            }else{
                swap(nums,index,maxIndex);
                index = maxIndex;
                l = (index<<1)+1;
                r = l+1;
            }
        }
//        int left  = (index<<1)+1;
//        while (left<size){
//            int right = left+1;
//            int bigIndex = right<size&&nums[left]<nums[right]?right:left;
//            bigIndex = nums[index]>nums[bigIndex]?index:bigIndex;
//            if(bigIndex==index){
//                break;
//            }
//            swap(nums,index,bigIndex);
//            index = bigIndex;
//            left = (index<<1)+1;
//        }
    }


    //构建大跟堆
    public void heapInsert(int[] nums,int index){
        int parentIndex = (index-1)/2;
        while (parentIndex>=0&&nums[index]>nums[(index-1)/2]){
            swap(nums,index,(index-1)/2);
            index = (index-1)/2;
        }
//        while (nums[index]>nums[(index-1)/2]){
//            swap(nums,(index-1)/2,index);
//            index = (index-1)/2;
//        }
    }

    public void swap(int[] arr, int j, int i) {
        int temp=arr[i];
        arr[i]=arr[j];
        arr[j]=temp;
    }
}
